import java.util.Arrays;

public class YetAnotherHashMap {

    Integer[] keys;
    Integer[] vals;

    public int capacity;
    final int INITIAL_CAPACITY_POW = 19;

    public YetAnotherHashMap() {
        capacity = 2 << INITIAL_CAPACITY_POW;
        keys = new Integer[capacity];
        vals = new Integer[capacity];
    }

    public void put(Integer k, Integer v) {
        int index = indexFor(hash(k));
        int originalIndex = index;

        //open addressing :(
        while ((keys[index] != null) && (keys[index] != k)) {
            index = (index + 1) & (capacity - 1);
            if (index == originalIndex) {
                //TODO: Implement resizing.
                throw new RuntimeException("Out of capacity.");
            }
        }

        addEntry(index, k, v);
    }

    private void addEntry(int index, Integer k, Integer v) {
        keys[index] = k;
        vals[index] = v;
    }

    public Integer get(Integer k) {
        int index = indexFor(hash(k));
        int originalIndex = index;

        //open addressing :(
        while (!k.equals(keys[index])) {
            index = (index + 1) & (capacity - 1);
            if (index == originalIndex) {
                break;
            }
        }

        return vals[index];
    }


    public int standardHash(Integer k) {
        int h = 0;

        h ^= k.hashCode();

        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    public int strangeHash(Integer k) {
        return (hash(k) >>> 2) << 2;
    }

    public int hash(Integer k) {
        return standardHash(k);
//        return strangeHash(k);
//        return k.hashCode();
    }

    private int indexFor(int h) {
        return h & (capacity - 1);
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder("[");

        for (int i = 0; i < capacity; i++) {
            if (keys[i] != null) {
                s.append(keys[i] + "=" + vals[i] + ", ");
            } else {
                s.append("n=n, ");
            }
        }
        return s.append("]").toString();
    }

    public void touch() {
        Arrays.toString(keys);
        Arrays.toString(vals);
    }

}
